模拟赛题解/2025.10.18 模拟赛

T1-大水题（water）

题面

栋栋给定一个字符集为 $\{0,1,2\}$ 的字符串。

现在你可以执行以下 $3$ 种操作任意次：

• 选择任意一个 $2$，将其替换成 $0$ 或 $1$。
• 选择两个相邻的 $0$，将其删除，并连接剩下的字符串。
• 选择两个相邻的 $1$，将其删除，并连接剩下的字符串。

请帮栋栋求出可能得到的字符串的最小长度。

$1\leq|s|\leq2\times10^6$。

题解

我们发现 $00$ 和 $11$ 要分开来讨论很烦，但是注意到一个性质：

每次删除都是两两进行，所以删除后每个点的奇偶性不变，两个能被一起删除的点一定是奇偶性不同的。

所以考虑直接把所有偶数位取反，问题就变成了可以删除一对 $10$ 或 $01$，把 $0$ 视为 $-1$，则可证和为零的区间一定能被消除。

所以直接计算除了 $2$ 之外的总和，用 $2$ 尽量去降低总和的绝对值（即最终剩下的字符串长度）即可。

时间复杂度 $O(n)$。

T2-大水题（water）

题面

对于正整数序列 $a$，栋栋定义 $f(a)$ 为最大的 $k$ 使 $a$ 可以被划分为 $k$ 个连续子段， 使任意两段元素构成的集合无交，即任意两段没有相同的元素。

如序列 $a=\{1,3,4,3,2\}$ 可以被划分为 $\{1\},\{3,4,3\},\{2\}$ 这 $3$ 段，且没有更优的划分方式，所以 $f(a)=3$。

现在要求你对于任意长度为 $n$，值域在 $[1,m]$ 中的正整数序列 $a$ 求出 $f(a)$ 之和。答案对 $10^9+7$ 取模。

$1\leq n\leq 5000,1\leq m\leq 10^9$。

题解

对于给定的序列，划分方法是显然是，直接从左到右贪心进行即可。

Subtask 1

$O(m^n)$ 枚举序列，然后线性求答案。

Subtask 2

$f(a)$ 只能等于 1 或 2。简单算出 $f(a) = 2$ 的情况数，然后就能算出答案了。

Subtask 3

总贡献问题，考虑对贡献算方案。关键是，你的贡献是什么。如果以一个段为贡献，能引导出一些做法。

考虑对于一个段，我们如何确定包含它的序列个数。首先要求这个段不能被分隔成若干小段，不然肯定会算重。其次我们需要知道段的长度和种类数。假设其长度为 $x$，种类数为 $y$，包含它的序列个数为：

$$\sum_{i=0}^{n-x} \sum_{j=0}^{m-y} \sum_{k=0}^{j} \begin{cases} i \\ k \end{cases} \quad \begin{cases} n-i \\ j-k \end{cases}$$

接下来要求长度为 $x$，种类数为 $y$ 的不可分割段的数量，设为 $f_{x,y}$。考虑容斥，以第一个不可分割段区分方案。

$$f_{x,y} = \begin{cases} x \\ y \end{cases} - \sum_{i=1}^{x-1} \sum_{j=1}^{y} f_{i,j} \begin{cases} x - i \\ y - j \end{cases}$$

将 $f$ 乘上方案就可以算答案了，注意每个种类还需要分配一个具体的颜色。种类数一定不超过序列长度，第二维实际上是 $n$ 级别，时间复杂度 $O(n^4)$。

Subtask 4-5

有 $O(n^3)$ 的做法，但是难度远大于正解，也和正解没关系，不多说。

Subtask 6

依旧枚举贡献，但是这一次不以段为贡献，而是以分段点为贡献，因为 $f$ 也等于分段点的个数。考虑求 $f$ 的过程，什么样的点可以分段？一定是 $[1, i]$ 和 $[i+1, n]$ 无交的 $i$ 可以作为分段点，这个也是非常容易理解的。所以我们直接计算 $i$ 作为分段点的方案。

$$\sum_{i=1}^{n} \sum_{j=1}^{m} A_m^j \begin{cases} i \\ j \end{cases} (m-j)^{n-i}$$

同样的，$j$ 的范围实际是 $n$。时间复杂度 $O(n^2)$。

T3-送分题（score）

题面

小 X 喜欢思考关于最大前缀和的问题。她认为一个长度为 $n$ 的序列 $A$ 的最大前缀和为 $\forall j\in [1,n],\sum^j_{i=1}A_i$ 的最大值。

同时，她喜欢用 $a_{l,r}$ 表示序列 $a$ 的连续子序列 $[a_l,a_{l+1},\dots,a_r]$。

小 X 有一个长度为 $n$ 的序列 $a$ 和 $q$ 次询问，每次询问给出 $l,r$。对于每次询问，她想要知道 $a_{l,r}$ 的所有连续子序列的最大前缀和的和。

由于小 X 无法与你直接交流，她的询问将以一种特殊的方式给出，你的回答也需要以特殊形式输出。具体见输入输出格式。

$n\leq 10^6,q\leq 10^7,S,A,B,P\leq 10^9，tp\leq 1$。

题解

首先，处理出前缀和数组 $s_i$，区间 $[l, r]$ 的最大前缀和即为 $-s_{l-1} + \max_{i=l}^{r} s_i$。

对于询问 $[l, r]$，要求 $[L, R] \in [l, r]$ 的最大前缀和。其中 $-s_{L-1}$ 的项是容易预处理前缀和然后 $O(1)$ 计算的。只考虑后面的一项，问题就成了任意子区间最大值的和。

时间复杂度 $O((n+q) \log n)$。

关键词：扫描线，历史版本和。

在从左往右扫描右端点 $r$ 的过程中，是容易使用单调栈 + 线段树 维护出每个左端点 $l$ 的答案的。每个询问会查询 $L \in [l, r], R \in [l, r]$，对于 $L$ 是查线段树上一个区间，$R$ 则用历史版本和差分得到。需要写主席树。

时间复杂度 $O(n \log n + q)$或$O(n + q)$。

先考虑 $L \in [l, r], R = r$，即询问区间的所有后缀的贡献。

模拟一个左端点 $L = r$，然后往前移动的过程。过程中维护最大值，并贡献答案。

对于每个点，找出其左边第一个大于它的点。这样的关系构成了树。并且上述过程中最大值的变化过程构成了一条向上的链。记 $[L, R]$ 最大值为 $s_p$，则这条链从 $R$ 开始，到 $p$ 结束。发现链上的点，除了 $p$ 之外点的贡献是可以预处理的，点 $x$ 的贡献为 $s_x \times (x - f a_x)$。于是可以预处理树上前缀和之后再差分，对于 $p$ 的贡献单独处理。于是 $L \in [l, r], R = r$ 的部分贡献为

$$sum_R - sum_p + s_p \times (p - L + 1)$$

发现对于 $L \in [l, r], R = r$ 的部分，贡献只与最大值有关。仔细思考一下，在解决一个 $[L, R]$ 的问题时，也可以视作只关注了最大值处，所以理论上，解决单个区间的复杂度与解决后缀区间的复杂度是几乎一致的。之前的问题相当于计算每个后缀区间的"单个区间"之和，之后的问题相当于计算每个前缀区间的"后缀区间"之和。

聪明的你想必不再想听到重复的过程了。

于是只需要求出区间最大值的位置，就可以 $O(1)$ 计算答案了。

用 ST 表预处理带 $\log$，用一些高级的东西就可以线性了。

T4-计数题（count）

题面

栋栋有一个下标为 $[0,n)$ 的序列 $A$，我们并不知道 $A$ 中任意一个元素的值。

给定在 $A$ 上建立的一棵广义线段树。对于线段树的每个非叶子节点 $i$，设它管辖 $[l_i,r_i)$。它有一个属性 $m_i(l_i<m_i<r_i)$ 表示其左儿子管辖的区间为 $[li,mi)$，其右儿子管辖的区间为 $[mi,ri)$ 。规定根节点管辖的区间为 $[0,n)$。

容易发现这棵线段树有 $n − 1$ 个非叶子节点和 $n$ 个叶子。

定义一个区间 $[L,R)$ 的权值为 $\sum^{R−1}_{i=L}A_i$。

现在给出 $m$ 个区间 $[L_i,R_i)$。易知这棵线段树节点的子集共有 $2^{2n−1}$ 种，请你求出其中有多少个集合 $S$ 满足：如果已知 $S$ 中所有节点的管辖区间的权值，则 $m$ 个区间的权值都能唯一确定。答案对 $998244353$ 取模。

区间 $[l,r)$ 的权值能唯一确定指：存在某种运算已知区间权值的方法，使得到的一定是 $[l,r)$ 的权值。

例如：已知 $[3,5),[5,7)$ 的权值，就能确定 $[3,7)$ 的权值。已知 $[4,8),[4,5)$ 的权值，就能确定 $[5,8)$ 的权值。然而知道 $[3,5),[4,6)$ 的权值并不能确定 $[3,6)$ 的权值。

$1\leq n,m\leq 2\times 10^5,0\leq L_i<R_i\leq n$。

题解

性质1：将 $S$ 中的区间 $[l, r]$ 看成一条 $(l, r)$ 间的无向边，那么 $[L, R]$ 能被唯一确定当且仅当 $L, R$ 连通。$l \to r$ 表示增加这一部分和，$l \leftarrow r$ 表示减少这一部分和，一条路径一定对应一个能确定的区间。

Subtask 1&2：

枚举 $S$，然后连边判断连通性即可。时间复杂度 $O(2^{2n-1}(n+m))$

Subtask 3：

考虑在线段树上做树形 DP，决策当前节点是否选择。考虑在 $L_i, R_i$ 的 $LCA$ 处匹配它们。

需要两种状态：

$g_u$ 表示 $l_u, r_u$ 连通，且 $u$ 子树内未匹配的单点都与 $l_u, r_u$ 中的一个连通。

$f_u, s$ 表示 $l_u, r_u$ 不连通，$u$ 子树内未匹配的单点是与 $l_u$ 还是 $r_u$ 连通。

如果有一个未匹配点不与 $l_u$ 或 $r_u$ 连通，那它将不可能去到 $[l_u, r_u]$ 以外的结点，一定无法和另一个点匹配，是一个非法的状态。

直接转移，视实现应该是一个和 $O(n2^m)$ 到 $O(n2^{2m})$ 之间的算法，可以通过。

Subtask 4

真的需要找正每一个单点是和 $l$ 还是 $r$ 连通吗？

性质2：如果 $l_u, r_u$ 不连通，则 $[l_u, r_u]$ 内和 $l_u$ 连通的节点都在和 $r_u$ 连通的节点的左边：

既一定是上图的情况。如果是下图的情况，说明 $l_u, r_u$ 直接连通。感性理解一下，一条连边其实将内部划成一个封闭的区域，内部的点想出去一定要和端点连通。

同样需要两种状态：

$g_u$ 表示 $l_u, r_u$ 连通，且 $u$ 子树内未匹配的单点都与 $l_u, r_u$ 中的一个连通。

$f_{u,j}$ 表示 $l_u, r_u$ 不连通，最后一个与 $l_u$ 连通的点的位置是 $j$。且 $\leq j$ 的未匹配的单点都与 $l_u$ 连通，$> j$ 的未匹配的单点都与 $r_u$ 连通。

考虑转移：

首先是 $l_u, r_u$ 连边的情况：

$g_{ls} : g_{rs} \rightarrow g_u$

$g_{ls} : f_{rs,j} \rightarrow g_u$

$f_{ls,j} : g_{rs} \rightarrow g_u$

$f_{ls,j} : f_{rs,k} \rightarrow g_u$（增加不连通段，$[j+1,k]$ 中所有未匹配的单点都是连通的，要求 $[j+1,k]$ 中不存在匹配点在 $[j+1,k]$ 之外的点）

$l_u, r_u$ 不连边的情况：

$g_{ls} : g_{rs} \rightarrow g_u$

$g_{ls} : f_{rs,j} \rightarrow f_{u,j}$

$f_{ls,j} : g_{rs} \rightarrow f_{u,j}$

$f_{ls,j} : f_{rs,k} \rightarrow f_{u,j}$（增加不连通段，$[j+1,k]$ 中所有未匹配的单点都是连通的，要求 $[j+1,k]$ 中不存在匹配点在 $[j+1,k]$ 之外的点）

暴力做这个 DP 就是 $O(n^2)$ 的。

Subtask 5

性质 3：$f_{ls,j} \cdot f_{rs,k}$ 可以转移当且仅当跨过 $[j, j+1)$ 和 $[k, k+1]$ 的询问区间集合相同。证明显然。

所以可以先用和哈希，把下标分类。直接用下标等价类代替 $f$ 的第二维。

现在的 DP 就是 左边乘系数 + 右边乘系数 + 左右对应位置乘。显然 $f_u$ 里有值的点只有 $sz_u$ 个，哈希表启发式合并即可。

时间复杂度：$O(n \log n)$。